import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Demo01 {

    static int[] w;//物品的重量
    static int[] v;//物品的价值
    static int maxValue = 0;//最大价值

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();//物品个数
        int m = sc.nextInt();//背包容量

        w = new int[n];//物品的重量
        v = new int[n];//物品的价值
        for (int i = 0; i < n; i++) {
            w[i] = sc.nextInt();
            v[i] = sc.nextInt();
        }

        for (int i = 0; i < n; i++) {
            List<Integer> list = new ArrayList<>();
            list.add(i);
            dfs(i, list, n, m);
        }
        System.out.println(maxValue);

    }

    public static void dfs(int x, List<Integer> list, int n, int m) {
        if (x >= n) return;

        System.out.println("组合：" + list);
        int sumV = 0, sumW = 0;
        for (int i = 0; i < list.size(); i++) {
            int index = list.get(i);
            sumV += v[index];
            sumW += w[index];
        }
        //比较组合起来的物品重量
        if (sumW <= m) {//说明背包可以放得下物品
            maxValue = Math.max(sumV, maxValue);
        }
        System.out.println("组合的总价值：" + sumV + " 组合的总重量：" + sumW + " 最优价值：" + maxValue);
        int s = x + 1;
        list.add(s);
        dfs(s, list, n, m);
    }
}
